
//41.太平洋大西洋水流问题
class Solution {
public:
    vector<vector<int>> pacificAtlantic(vector<vector<int>>& nums) {
        //分开处理,依次统计能够流向太平洋和大西洋的位置,在求其交集
        //水从高出往低处流,最终一定留到大洋中,那就可以中大洋中出发,向高出走,只要是走到的位置一定都是可以留到大洋中的位置

        int dx[]={-1,1,0,0};  
        int dy[]={0,0,-1,1};
        int n=nums.size(),m=nums[0].size();
        vector<vector<int>> vistpa(n,vector<int>(m));
        vector<vector<int>> vistat(n,vector<int>(m));
        set<pair<int,int>> stpa;
        set<pair<int,int>> stat;

        //进行递归,(x,y)是左边,st存储可以流入大洋的水流,vist存储已经到达过的位置
        function<void(int,int,set<pair<int,int>>&,vector<vector<int>>&)> dfs=[&](int x,int y,set<pair<int,int>>& st,vector<vector<int>>& vist)
        {
            if(vist[x][y]) return ;
            vist[x][y]=1;
            st.insert({x,y});  //将该位置存储起来
            for(int k=0;k<4;k++)
            {
                int a=x+dx[k],b=y+dy[k];
                if(a>=0&&a<n&&b>=0&&b<m&&nums[a][b]>=nums[x][y]) dfs(a,b,st,vist);
            }    
        };
        //分别从上下左右找
        for(int i=0;i<m;i++)
        {
            dfs(0,i,stpa,vistpa);
            dfs(n-1,i,stat,vistat);
        }
        for(int i=0;i<n;i++)
        {
            dfs(i,0,stpa,vistpa);
            dfs(i,m-1,stat,vistat);
        }

        //找交集
        vector<vector<int>> ret;
        for(auto& pa:stpa){
            if(stat.count(pa)) ret.push_back({pa.first,pa.second});
        }
        return ret;
    }
};